The presence of the genus Cuon during the Pleistocene of Java is attested by the endemic species C. sangiranensis and C. crassidens, sometimes classified as C. alpinus, a species that is also part of the Holocene fauna and has persisted until today. The current study revises the fossil canid material from the Sangiran Dome, previously assigned variously to C. sangiranensis, C. crassidens, C. alpinus, C. javanicus, and C. trinilensis. It aims to reinvestigate the arrival of Cuon in Java, in particular in relation to the late early Pleistocene endemic canid of Java: the Cuon-sized Xenocyon trinilensis, which had evolved in situ on Java from the large X. merriami, and which could be a potential competitor to early Cuon in case of contemporaneity. We found that a mandible fragment from Pandejan (holotype of C. crassidens) shows a morphology typical for C. alpinus. However, a maxilla and a mandible from the Bapang Formation at Sangiran, including the holotype of C. sangiranensis, is here assigned to the early dhole species C. priscus. Our results indicate that Cuon was already present in Java during the early middle Pleistocene and probably arrived as part of the immigration events during the Kedung Brubus faunal stage. Since X. trinilensis and Cuon are both hypercarnivorous medium-sized dogs, similar ecological niches are expected for both species. Thus, X. trinilensis probably was outcompeted and replaced by C. priscus. In turn, the latter species was replaced by the extant species, C. alpinus, during the Nangdong faunal stage, likely as part of the next immigration phase, which then disappeared during the tropical rainforest fauna of the Punung faunal stage and re-entered at the onset of the Holocene.